package 每日一题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * 1054. 距离相等的条形码
 * 在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。
 *
 * 请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：barcodes = [1,1,1,2,2,2]
 * 输出：[2,1,2,1,2,1]
 * 示例 2：
 *
 * 输入：barcodes = [1,1,1,1,2,2,3,3]
 * 输出：[1,3,1,3,2,1,2,1]
 *
 *
 * 提示：
 *
 * 1 <= barcodes.length <= 10000
 * 1 <= barcodes[i] <= 10000
 */
public class D220720_T1054 {

    class Element {
        int numValue;
        int count;

        public Element(int numValue) {
            this.numValue = numValue;
            count = 1;
        }

        public void add(int i) {
            count += i;
        }
    }

    public int[] rearrangeBarcodes(int[] barcodes) {


        Arrays.sort(barcodes);

        ArrayList<Element> elements = new ArrayList<>();
        Element element = new Element(barcodes[0]);
        for (int i = 1; i < barcodes.length; i++) {

            if (barcodes[i] == element.numValue) {
                element.add(1);
            } else {
                elements.add(element);
                element = new Element(barcodes[i]);
            }

        }
        elements.add(element);

        elements.sort(new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return o2.count - o1.count;
            }
        });

        int[] ans = new int[barcodes.length];
        int index = 0;
        int elementIndex = 0;
        for (; index < ans.length; ) {
            Element element1 = elements.get(elementIndex);

            ans[index] = element1.numValue;
            index += 2;
            element1.count -= 1;
            if (element1.count == 0) {
                elementIndex++;
            }
        }

        index = 1;
        for (; index < ans.length; ) {
            Element element1 = elements.get(elementIndex);

            ans[index] = element1.numValue;
            index += 2;
            element1.count -= 1;
            if (element1.count == 0) {
                elementIndex++;
            }
        }

        return ans;

    }



    public static void main(String[] args) {
        D220720_T1054 d220720_t1054 = new D220720_T1054();
        d220720_t1054.rearrangeBarcodes(new int[]{1, 1, 2});
    }


}
